﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MD5_Trie_Demo
{
    public class Trie
    {
        private Trie[] _children;
        private bool _isEnd;

        public Trie()
        {
            _children = new Trie[16];
            _isEnd = false;
        }

        public void Insert(string md5Hash)
        {
            Trie node = this;
            char[] chars = md5Hash.ToCharArray();
            for (int i = 0; i < chars.Length; i++)
            {
                char c = chars[i];
                int position = GetPosition(c);
                if (node._children[position] == null)
                {
                    node._children[position] = new Trie();
                }

                node = node._children[position];
            }

            node._isEnd = true;
        }

        public bool Search(string key)
        {
            Trie? node = SearchPrefix(key);
            return node != null && node._isEnd;
        }

        public bool StartWith(string prefix)
        {
            return SearchPrefix(prefix) != null;
        }

        private Trie? SearchPrefix(string prefix)
        {
            Trie node = this;
            char[] chars = prefix.ToCharArray();
            for (int i = 0; i < chars.Length; i++)
            {
                char c = chars[i];
                int position = GetPosition(c);

                if (node._children[position] == null) return null;

                node = node._children[position];
            }

            return node;
        }

        private int GetPosition(char c) => char.ToLower(c) switch
        {
            '0' => 0,
            '1' => 1,
            '2' => 2,
            '3' => 3,
            '4' => 4,
            '5' => 5,
            '6' => 6,
            '7' => 7,
            '8' => 8,
            '9' => 9,
            'a' => 10,
            'b' => 11,
            'c' => 12,
            'd' => 13,
            'e' => 14,
            'f' => 15,
            _ => throw new InvalidOperationException($"不支持字符：{c}")
        };
    }
}
